/*
 * 【leetcode】94题代码 存档
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int white = 0;
    int gray = 1;

    //一个动态数组存储各个结点的值
    int *re = (int*) malloc(100 * sizeof(int));
    int cnt = 0;    //计数

    //一个存放颜色的栈
    int *color = (int*) malloc(100 * sizeof(int));
    //一个存放结点的栈
    struct TreeNode **s = (struct TreeNode**) malloc(100 * sizeof(struct TreeNode*));
    int top = 0;

    //根结点及其颜色同步压入对应的栈
    s[top] = root;
    color[top] = white;
    top++;
    //栈不为空时循环
    while (top != 0) {
        //结点及其颜色出栈
        int c = color[top - 1];
        struct TreeNode *node = s[top - 1];
        top--;
        if (NULL == node)
            continue;
        if (c == white) {
            color[top] = white;
            s[top++] = node->right;

            color[top] = gray;
            s[top++] = node;

            color[top] = white;
            s[top++] = node->left;
        }
        else 
            re[cnt++] = node->val;
    }

    *returnSize = cnt;
    return re;
}

struct TreeNode* createBinaryTree(int* arr, int size) {
    if (size == 0 || arr[0] == -1) return NULL; // -1表示空节点

    // 创建根节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = arr[0];
    root->left = root->right = NULL;

    // 使用队列辅助构建二叉树
    struct TreeNode** queue = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;

    int index = 1;
    while (front < rear && index < size) {
        struct TreeNode* current = queue[front++];

        // 处理左子树
        if (index < size && arr[index] != -1) {
            current->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            current->left->val = arr[index];
            current->left->left = current->left->right = NULL;
            queue[rear++] = current->left;
        }
        index++;

        // 处理右子树
        if (index < size && arr[index] != -1) {
            current->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            current->right->val = arr[index];
            current->right->left = current->right->right = NULL;
            queue[rear++] = current->right;
        }
        index++;
    }

    free(queue);
    return root;
}

// test function
void test01() {
    // 测试用例：[1,null,2,3] 表示为 [1,-1,2,-1,-1,3]
    int input[] = {1, -1, 2, -1, -1, 3};
    int size = sizeof(input)/sizeof(input[0]);
    
    struct TreeNode* root = createBinaryTree(input, size);
    
    int returnSize;
    int* result = inorderTraversal(root, &returnSize);
    
    printf("中序遍历结果: ");
    for(int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    
    free(result);
    // 实际使用时需要添加释放树内存的函数
}

int main() {
    test01();
    return 0;
}
